package ArrayList;

import java.util.*;

/**
 * @Classname JZ03数组中重复的数字
 * @Description TODO
 * @Date 2022/12/5 14:10
 * @Created by xjl
 */
public class JZ03数组中重复的数字 {

    /**
     * @description 原地交换的方式来实现
     * 题目说明尚未被充分使用，即 在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内 。 此说明含义：数组元素的 索引 和 值 是 一对多 的关系。
     * 因此，可遍历数组并通过交换操作，使元素的 索引 与 值 一一对应（即 nums[i]=inums[i]=i ）。因而，就能通过索引映射对应的值，起到与字典等价的作用。
     *
      * @param: nums
     * @date: 2022/12/5 14:30
     * @return: int
     * @author: xjl
    */
    public int findRepeatNumber(int[] nums) {
       int index=0;
       while (index<nums.length){
           // 表示在正确的位置上的数字就可以往后走
           if (nums[index]==index){
               index++;
               continue;
           }
           // 判断如果当前的数据在原来的位置上是相等的 那就表示有的重复的存在
           if (nums[nums[index]]==nums[index]){
               return nums[index];
           }else {
               int tmp=nums[index];
               nums[index]=nums[tmp];
               nums[tmp]=tmp;
           }
       }
       return -1;
    }


    /**
     * @description 利用数组拍的方式 然后在遍历 如果判断当前是否与后面一个相同 那就返回该值
     * 时间：nlog(n)
      * @param: nums
     * @date: 2022/12/5 14:15
     * @return: int
     * @author: xjl
    */
    public int findRepeatNumber1(int[] nums) {
        Arrays.sort(nums);
        for (int i=0;i<nums.length-1;i++){
            if (nums[i]==nums[i+1]){
                return nums[i];
            }
        }
        return -1;
    }

    /**
     * @description  利用set 来判断 是否是该重复的元素
     * 时间为 n
      * @param: nums
     * @date: 2022/12/5 14:16
     * @return: int
     * @author: xjl
    */
    public int findRepeatNumber2(int[] nums) {
        Set<Integer> set=new HashSet<>();
        for (int i:nums){
            if (!set.contains(i)){
                set.add(i);
            }else {
                return i;
            }
        }
        return -1;
    }

    /**
     * @description 利用HashMap的方式来统计元素的每一个的个数
      * @param: nums
     * @date: 2022/12/5 14:17
     * @return: int
     * @author: xjl
    */
    public int findRepeatNumber3(int[] nums) {
        HashMap<Integer,Integer> map=new HashMap<>();
        for (int i:nums){
            if (!map.containsKey(i)){
                map.put(i,1);
            }else {
                return i;
            }
        }
        return -1;
    }
}
